package BF_DP;

public class Test4 {
    /*
    * N 与 M 描述了一个网格
    * i 和 j 代表了起始位置
    * k 代表能走 k 步
    * 问 : 在随机的只能上下左右走的情况下 ,  有多大的概率, 走完k步还在网格中?*/
    public static String bob1(int N,int M,int i,int j,int k){
        long all = (long) Math.pow(4,k);
        long live = process(N,M,i,j,k);
        long gcd = gcd(all,live);
        //因为要表示最简化的形式
        return String.valueOf((live / gcd) + " /" + (all / gcd));
    }
    //N*M 的区域,在(i,j)的位置,走 K步,获得的方法数
    public static long process(int N,int M ,int i,int j,int k){
        if ( i < 0 || i ==N || j <0 || j ==M){
            // 越界 直接0
            return 0;
        }
        if (k == 0){
            // i , j 没越界
            return 1;
        }
        long live =process(N,M,i-1,j,k-1);
        live += process(N,M,i+1,j,k-1);
        live += process(N,M,i,j+1,k-1);
        live += process(N,M,i,j-1,k-1);
        return live;
    }
    public static long gcd(long m,long n){
        //最大公约数???
        return n == 0 ? m:gcd(n,m%n);
    }
//    改动态规划 - 和象棋那个没区别,只是现在这个改4个位置
    public static String bob2(int N,int M,int i,int j,int k){
        /*没看懂为什么 这个dp数组 要扩大*/
        int[][][] dp = new int[N+2][M+2][k+1];
        for (int row = 1; row <= N ; row++) {
            for (int col = 1; col <= M ; col++) {
                dp[row][col][0] = 1;
            }
        }
        for (int rest = 1; k <= k; k++) {
            for (int row = 1; row <= N; row++) {
                for (int col = 1; col <= M; col++) {
                    dp[row][col][rest] = dp[row-1][col][rest-1];
                    dp[row][col][rest] = dp[row+1][col][rest-1];
                    dp[row][col][rest] = dp[row][col-1][rest-1];
                    dp[row][col][rest] = dp[row][col+1][rest-1];
                }
            }
        }
        long all = (long) Math.pow(4,k);
        long live = dp[i+1][j+1][k];
        long gcd = gcd(all,live);
        return String.valueOf((live / gcd) + " /" + (all / gcd));
    }

}
